﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortOf
{
    class BubbleSort
    {
        /*
         * Sort an array in ascending order
         */
        public static void SortAscending<T>(T[] array) where T : IComparable
        {
            Sort(array, false);
        }

        /*
         * Sort an array in descending order
         */
        public static void SortDescending<T>(T[] array) where T : IComparable
        {
            Sort(array, true);
        }

        /*
         * Sort the array in ascending or descending order. Used internally.
         */
        private static T[] Sort<T>(T[] array, bool descending) where T : IComparable
        {
            #if DEBUG
                String text = "Start:\n";
                foreach (T item in array) text += (item + " ");
                Console.WriteLine(text);
                int totalNumberOfSwaps = 0; // counts the total number of swaps made
            #endif

            int outer;
            // we need one pass less than the number of items in the array
            for (outer = array.Length - 1; outer > 0; outer--)
            {
                int passNumberOfSwaps = 0; // counts the number of swaps made this pass

                for (int inner = 0; inner < outer; inner++)
                {
                    // if sorting in descending order check if the negative of the current item is
                    // bigger than the next, which is the same as checking if it is smaller.
                    if (((descending ? -1 : 1) * array[inner].CompareTo(array[inner + 1])) > 0)
                    {
                        // swap the two items
                        T temp = array[inner];
                        array[inner] = array[inner + 1];
                        array[inner + 1] = temp;

                        passNumberOfSwaps++;
                    }
                }

                #if DEBUG
                    totalNumberOfSwaps += passNumberOfSwaps;
                    text = "Pass: " + (array.Length - outer) + "\n";
                    foreach (T item in array) text += (item + " ");
                    Console.WriteLine("\n" + text + "\n" + passNumberOfSwaps + " swaps made.");
                #endif

                // if no swaps here made this pass, stop prematurely to save time
                if (passNumberOfSwaps == 0)
                {
                    #if DEBUG
                        Console.WriteLine("No more swaps detected since last pass. Stopping...");
                        Console.WriteLine("\nDone!\n" + (array.Length - outer) + "/" + (array.Length - 1) + " passes used.\n" + totalNumberOfSwaps + " swaps made.");
                        Console.ReadLine();
                    #endif

                    return array;
                }
            }

            #if DEBUG
                Console.WriteLine("\nDone!\n" + (array.Length - outer - 1) + "/" + (array.Length - 1) + " passes used.\n" + totalNumberOfSwaps + " swaps made.");
                Console.ReadLine();
            #endif

            return array;
        }
    }
}
